package com.wanghe.leetcode.jianzhioffer;

import java.util.HashMap;
import java.util.Map;

/**
 * 面试题01.05 一次编辑
 * https://leetcode-cn.com/problems/one-away-lcci/
 */
public class Problem0105 {

    private Map<String, Integer> results = new HashMap<>();

    public static void main(String[] args) {
        Problem0105 problem0105 = new Problem0105();
        String s1 = "a";
        String s2 = "ab";
        System.out.println(problem0105.oneEditAway(s1, s2));
    }

    private boolean oneEditAway(String first, String second) {
        int d = distance(first, second, first.length(), second.length());
        if (d <= 1) {
            return true;
        }
        return false;
    }

    private int distance(String s1, String s2, int p1, int p2) {

        String key = "" + p1 + "#" + p2;
        Integer savedResult = results.get(key);
        if (savedResult != null) {
            return savedResult;
        }

        if (0 == p1) {
            return p2;
        }
        if (0 == p2) {
            return p1;
        }
        char c1 = s1.charAt(p1 - 1);
        char c2 = s2.charAt(p2 - 1);
        if (c1 == c2) {
            return distance(s1, s2, p1 - 1, p2 - 1);
        }
        savedResult = min3Values(distance(s1, s2, p1 - 1, p2) + 1,
                distance(s1, s2, p1, p2 - 1) + 1,
                distance(s1, s2, p1 - 1, p2 - 1) + 1);

        results.put(key, savedResult);
        return savedResult;
    }

    private int min3Values(int v1, int v2, int v3) {
        int tmp = Integer.MAX_VALUE;
        if (v1 < tmp) {
            tmp = v1;
        }
        if (v2 < tmp) {
            tmp = v2;
        }
        if (v3 < tmp) {
            tmp = v3;
        }
        return tmp;
    }
}
